/**
 * @file function definitions for SQ_ring.h
 */

#include <math.h>
#include "SQ_ring.h"


/**
 * finds and returns the weight (i.e. number of non-zero elements) in a SQ polynomial
 *
 **/
int coeff_weight(const ZZ_pEX& poly)
{
	int poly_deg = deg(poly);
	int weight=0;
	for(int i=0;i<=poly_deg;i++)
		if( !IsZero(coeff(poly,i)) ) weight++;

	return weight;
}

/**
 * finds and returns the weight (i.e. number of non-zero elements) in a vector in GF(q)
 * 
 **/
int coeff_weight(const vec_ZZ_pE& vec)
{
	int vec_len = vec.length();
	int weight=0;
	for(int i=0;i<vec_len;i++)
		if( !IsZero(vec[i]) ) weight++;

	return weight;
}

/**
 *   Finds the Frobenius Automorphism of an element
 *
 *   @a the element for which the mapping is done
 *   @p the characteristic of the base field
 *   @i the iterations of the mapping
 *
 *   @return outputs \sigma_{p}^{i}(a)=a^(p^i) 
 **/
ZZ_pE	FAuto_p(const ZZ_pE& a,ZZ p,long i)
{
	if(i == 0) return a;
	ZZ ZZ_ONE; 
	set(ZZ_ONE);	// ZZ_ONE = 1
	ZZ reduced_power = PowerMod(p,i, ZZ_pE::cardinality()-ZZ_ONE);	// make use of the fact that x^{q}=q to find power
	return power(a,reduced_power);	// return power(a,power(p,i))	
}

/**
 * (r)ight (mul)tiplies the first input skew polynomial by the second input skew polynomial.
 *
 * In this function, the Frobenius Automorphism is assumed over the skew ring. Also, lists of coefficients of the two polynomials can be specified for faster performance.
 *
 * @a the first input polynomial in the pre-defined skew polynomial ring
 * @b the second input polynomial in the pre-defined skew polynomial ring
 *
 **/
ZZ_pEX	SQ_mulr(const ZZ_pEX& a, const ZZ_pEX& b,int* coeff_list_a,int num_of_coeff_a,int* coeff_list_b,int num_of_coeff_b)
{
	ZZ_pEX result= 0*a;

	if(num_of_coeff_a == -1)
	{
		if(num_of_coeff_b == -1)
		{
			int DEG_of_b = (int) deg(b);
			for(int i=0;i<=DEG_of_b;i++)
				if(!IsZero(coeff(b,i)))
					result += (SQ_mulr_const(a,coeff(b,i)) << i);
		}
		else
		{
			for(int i=0;i<num_of_coeff_b;i++)
				result += (SQ_mulr_const(a,coeff(b,coeff_list_b[i])) << coeff_list_b[i]);
		}
	}
	else
	{
		if(num_of_coeff_b == -1)
		{
			int DEG_of_b = (int) deg(b);
			for(int i=0;i<=DEG_of_b;i++)
				if(!IsZero(coeff(b,i)))
					result += (SQ_mulr_const(a,coeff(b,i),coeff_list_a,num_of_coeff_a) << i);
		}
		else
		{
			for(int i=0;i<num_of_coeff_b;i++)
				result += ( SQ_mulr_const(a,coeff(b,coeff_list_b[i]),coeff_list_a,num_of_coeff_a) << coeff_list_b[i] );
		}
	}
	return result;
}

/**
 * (r)ight (mul)tiplies the input skew polynomial by the input (const)ant. 
 *
 * In this function, the Frobenius Automorphism is assumed over the skew ring.
 *
 * @a input polynomial from the defined skew polynomial ring
 * @b input constant element from the same ring
 *
 **/
ZZ_pEX SQ_mulr_const(const ZZ_pEX& a,const ZZ_pE& b,int* coeff_list_a,int num_of_coeff_a)
{
	if(IsZero(b))
		return ZZ_pEX();

	int DEG_of_a = (int) deg(a);
	ZZ_pEX a_CPY = a;

	if(num_of_coeff_a == -1)
	{
		for(int i=0;i<=DEG_of_a;i++)
		{
			if(!IsZero(coeff(a_CPY,i)))
				SetCoeff(a_CPY,(long) i, coeff(a_CPY,(long) i)*FAuto_p(b,ZZ_p::modulus(),(long) i) );
			else
				SetCoeff(a_CPY,(long) i, ZZ_pE() );
		}
	}	
	else
	{
		for(int i=0;i<num_of_coeff_a;i++)
		{
			if(!IsZero(coeff(a_CPY,coeff_list_a[i])))
				SetCoeff(a_CPY,(long) coeff_list_a[i], coeff(a_CPY,(long) coeff_list_a[i])*FAuto_p(b,ZZ_p::modulus(),(long) coeff_list_a[i]) );
			else
				SetCoeff(a_CPY,(long) coeff_list_a[i], ZZ_pE() );
		}
	}
	return a_CPY;
}


/**
 * (r)ight (div)ides the first skew polynomial input by the second skew polynomial input.
 *
 * In this function, the Frobenius Automorphism is assumed over the skew ring, i.e. f=Qg+R
 *
 * @f input polynomial from the defined skew polynomial ring
 * @g input constant element from the same ring
 * @Q the quotien passed back by reference
 * @R the residue passed back by reference
 *
 **/
void SQ_divr(const ZZ_pEX& f,const ZZ_pEX& g,ZZ_pEX& Q,ZZ_pEX& R)
{
	int n = (int) deg(f);
	int r = (int) deg(g);
	ZZ_pEX h;
	ZZ_pE b_r = coeff(g,r);
	ZZ_pEX f_cpy = f;

	// reset Q and R
        clear(Q); 
        clear(R);

	for(int i=n;i>=r;i--)
	{
		h= ZZ_pEX( i-r , coeff(f_cpy,i)/FAuto_p(b_r,ZZ_p::modulus(),(long) (i-r)) );  // h(i) = a_{i}/sigma^(i-r)(b_{r}) x^(i-r)
		Q+=h; // Q = h(n) + h(n-1) + ... + h(r)
		f_cpy= f_cpy - SQ_mulr(h,g); // f(i-1) = f(i) - h(i)g
	}
	R = f_cpy;
}

/**
 * (l)ight (div)ides the first skew polynomial input by the second skew polynomial input, i.e. f=gQ+R
 *
 * In this function, the Frobenius Automorphism is assumed over the skew ring.
 *
 * @f input polynomial from the defined skew polynomial ring
 * @g input constant element from the same ring
 * @Q the quotien passed back by reference
 * @R the residue passed back by reference
 *
 **/
void SQ_divl(const ZZ_pEX& f,const ZZ_pEX& g,ZZ_pEX& Q,ZZ_pEX& R,int* coeff_list_g,int num_of_coeff_g)
{
	int n = (int) deg(f);
	int r = (int) deg(g);
	ZZ_pEX h;
	ZZ_pE b_r = SQ_invAuto(coeff(g,r),r);
	
	ZZ_pEX f_cpy = f;

	// reset Q and R
        clear(Q); 
        clear(R);

	for(int i=n;i>=r;i--)
	{
		int i_minus_r = i-r;
		h= ZZ_pEX( i_minus_r , SQ_invAuto(coeff(f_cpy,i),r)/b_r );  // h(i) = a_{i}/sigma^(i-r)(b_{r}) x^(i-r)
		Q+=h; // Q = h(n) + h(n-1) + ... + h(r)
		if( num_of_coeff_g == -1 )
			f_cpy= f_cpy - SQ_mulr(g,h,NULL,-1,&i_minus_r,1); // f(i-1) = f(i) - h(i)g
		else
			f_cpy= f_cpy - SQ_mulr(g,h,coeff_list_g,num_of_coeff_g,&i_minus_r,1); // f(i-1) = f(i) - h(i)g
	}
	R = f_cpy;
}

/**
 * finds r'th inverse automorphism of an element
 *
 * This function asumes Frobenius Automorphism and returns \theta^{-r}(a)
 *
 * @a arbitrary element in the extension field
 * @r multiplicity of inverse
 *
 * @return returns r'th inverse automorphism of a
 *
 **/
ZZ_pE SQ_invAuto(const ZZ_pE& a,long r)
{
	if(IsZero(a))
		return a;

	ZZ ZZ_ONE; 
	set(ZZ_ONE);	// ZZ_ONE = 1
	ZZ reduced_power = PowerMod(to_ZZ(ZZ_pE::degree()),r, ZZ_pE::cardinality()-ZZ_ONE);	// make use of the fact that x^{q}=q to find power
	return power(a,reduced_power); // theta^{-r}(a) = a^{n^{r}} where n is dimension of the extension field;
}


/**
 * finds (g)reatest (c)ommon (r)ight (d)ivisor of the input polynomials over the skew polynomial ring
 *
 * @f_1 first input skew polynomial
 * @f_2 second input skew polynomial
 *
 * @return the gcrd
 *
 **/
ZZ_pEX SQ_gcrd(const ZZ_pEX& f_1,const ZZ_pEX& f_2)
{
	ZZ_pEX f_1cpy = f_1;
	ZZ_pEX f_2cpy = f_2;

	if( deg(f_2cpy) > deg(f_1cpy) ) swap(f_1cpy,f_2cpy);  // deg(f_1)>=deg(f_2)

	ZZ_pEX q_i,f_i;
	SetX(f_i); // f(i) = x

	for(int i=3;!IsZero(f_i);i++)
	{
		SQ_divr(f_1cpy,f_2,q_i,f_i); // f(i-2) = q(i)f(i-1) + f(i)
		f_1cpy = f_2cpy;	
		f_2cpy = f_i;		
	}

	return f_1cpy;
}


/**
 * Computes a polynomial raised to the input power (inefficient)
 *
 * @poly input skew polynomial
 * @exp the power to which the polynomial will be raised
 *
 * @return polynomial raised to the given power
 *
 **/
ZZ_pEX SQ_power(const ZZ_pEX& poly,int exp)
{
	ZZ_pEX poly_cpy = poly;
	if(exp == 0)	
	{
		ZZ_pEX identity;
		set(identity); // x = 1
		return identity;
	}
	if(exp % 2  == 0)
		return SQ_power(SQ_mulr(poly_cpy,poly_cpy),exp/2);
	else
		return SQ_mulr(SQ_power(SQ_mulr(poly_cpy,poly_cpy),exp/2),poly_cpy);
}





